use num_bigint::BigUint;
use once_cell::sync::Lazy;
use rand::Rng;
use std::cmp::max;
use std::sync::Mutex;

pub fn find_max_prime_factor(number: u128) -> u128 {
    *MAX_FACTOR.lock().unwrap() = 0;
    fac(number);
    *MAX_FACTOR.lock().unwrap()
}

static MAX_FACTOR: Lazy<Mutex<u128>> = Lazy::new(|| Mutex::new(0));

fn fac(mut x: u128) {
    {
        let mut max_factor = MAX_FACTOR.lock().unwrap();
        if x <= *max_factor || x < 2 { return; }
        if miller_rabin(x) {
            *max_factor = max(x, *max_factor);
            return;
        }
    }
    let mut p = x;
    while p >= x { p = pollard_rho(x); }
    while (x % p) == 0 { x /= p; }
    fac(x);
    fac(p);
}

fn gcd(a: u128, b: u128) -> u128 {
    if b == 0 {
        return a;
    }
    gcd(b, a % b)
}

fn quick_mul(a: u128, b: u128, m: u128) -> u128 {
    if let Some(res) = a.checked_mul(b) {
        return res % m;
    }

    let a = BigUint::from(a);
    let b = BigUint::from(b);
    let m = BigUint::from(m);
    let c = (a * b % m).to_u64_digits();

    let c = match c.len() {
        1 => c[0] as u128,
        2 => ((c[1] as u128) << 64) & (c[0] as u128),
        _ => 0,
    };
    c
}

fn quick_pow(a: u128, b: u128, m: u128) -> u128 {
    let mut res = 1;
    let mut a = a;
    let mut b = b;
    while b != 0 {
        if (b & 1) != 0 { res = quick_mul(res, a, m); }
        a = quick_mul(a, a, m);
        b >>= 1;
    }
    res
}

fn miller_rabin(p: u128) -> bool {
    if p < 2 { return false; }
    if p == 2 { return true; }
    if p == 3 { return true; }
    let mut d = p - 1;
    let mut r = 0;
    while d & 1 == 0 {
        r += 1;
        d >>= 1;
    }
    for _ in 0..10 {
        let mut rng = rand::thread_rng();
        let a = rng.gen_range(2..p);
        let mut x = quick_pow(a, d, p);
        if x == 1 || x == p - 1 { continue; }
        for _ in 0..r - 1 {
            x = quick_mul(x, x, p);
            if x == p - 1 { break; }
        }
        if x != p - 1 { return false; }
    }
    true
}

fn pollard_rho(x: u128) -> u128 {
    let mut s = 0;
    let mut t = 0;
    let mut rng = rand::thread_rng();
    let c = rng.gen_range(1..x);
    let mut goal = 1;
    loop {
        let mut val = 1;
        for step in 1..goal + 1 {
            t = (quick_mul(t, t, x) + c) % x;
            val = quick_mul(val, (t as i128 - s as i128).unsigned_abs(), x);
            if (step % 127) == 0 {
                let d = gcd(val, x);
                if d > 1 { return d; }
            }
        }
        let d = gcd(val, x);
        if d > 1 { return d; }
        goal *= 2;
        s = t;
    }
}